#ifndef ULIMIT_TREE_H
#define ULIMIT_TREE_H

#include "common.h"
#include "stack.h"

/**
 * This demo shows an implementation of 'left-child,right-sibling representation
 * for trees with unlimited children.
 * Actually this representation is somehow designed for linear storage.
 */

#define LINEAR_TREE_LIMIT_SIZE 100

/**
 * class UlimitLinearTree implemented a tree capable to store unlimited number of children.
 */
template< class T >
class UlimitLinearTree
{
    T data[LINEAR_TREE_LIMIT_SIZE];
    int father[LINEAR_TREE_LIMIT_SIZE];
    int child[LINEAR_TREE_LIMIT_SIZE];
    int sibling[LINEAR_TREE_LIMIT_SIZE];

    int rootPos;

    Stack<int> freePos;
public:
    UlimitLinearTree():rootPos(0)
    {
        try{
            // Add root node
            data[0] = -1;
            father[0] = -1;
            child[0] = -1;
            sibling[0] = -1;

            // Put remain free space to a stack for recycling convenience
            for( int i=LINEAR_TREE_LIMIT_SIZE-1; i>0; --i )
            {
                freePos.push(i);
            }
        }catch( Exception &e )
        {
            Exception ulte("Stack exceeded in UlimitLinearTree()");
            throw ulte;
        }
    }

    /**
     * @brief addChild
     * Add a child to given root
     * @param fatherPos
     * @param value
     * @return
     */
    int addChild( int fatherPos, T value )
    {
        try{
            ASSERT( fatherPos >=0);
            ASSERT( fatherPos<LINEAR_TREE_LIMIT_SIZE );

            // Allocate and init
            int leafPos = freePos.pop();
            data[leafPos] = value;
            father[leafPos] = fatherPos;
            child[leafPos] = -1;

            int siblingPos = child[fatherPos];
            child[fatherPos] = leafPos;
            sibling[leafPos] = siblingPos;

            return leafPos;
        }catch( Exception& e )
        {
            Exception treeExcept("Linear memory limit exceeded");
            throw treeExcept;
        }
        ASSERT( 0 );
        return -1;
    }

    void removeChild( int pos )
    {
        ASSERT( pos>0 && pos<LINEAR_TREE_LIMIT_SIZE );

        int fatherPos = father[pos];

        // Lucky enough, this is the first child
        if( child[fatherPos] == pos )
        {
            child[fatherPos] = sibling[pos];
        }
        else // It's among child 2-N
        {
            int siblingPos = child[fatherPos]; // Get its first sibling
            do{
                siblingPos = sibling[siblingPos];
            }while( sibling[siblingPos] != pos );

            sibling[siblingPos] = sibling[pos];
        }

        freePos.push(pos);
    }

    /**
     * @brief traverse
     * Traverse this tree and print them, default start from root pos
     * @param startPos
     */
    void traverse( int level = 0 , int startPos = 0 )
    {
        // Print spaces to tell level of the tree
        for( int i=0; i<level; i++ )
        {
            cout<<"  ";
        }

        cout<<data[startPos]<<endl;
        //cout<<"#pos="<<startPos<<endl;

        //Traverse child
        if( child[startPos] != -1 )
            traverse(level+1,child[startPos]);

        //Traverse sibling
        if( sibling[startPos] != -1 )
            traverse(level,sibling[startPos]);
    }

    void report()
    {
        cout<<"\nReport\n";
        for( int i=0; i< LINEAR_TREE_LIMIT_SIZE ; i++ )
        {
            if( father[i]>LINEAR_TREE_LIMIT_SIZE || father[i]<0 ) break;

            cout<<"f "<<father[i]<<" c "<<child[i]<<" s "<<sibling[i]<<" d "<<data[i]<<endl;
        }
    }

};

#endif // ULIMIT_TREE_H
